I. INTRODUCTION:
The digital analogues of handwritten signatures [1], [2] are used to identify unauthorized access or modifications to data and to authenticate the identity of the signer. In case of denial from signer that he has signed the document then the receiver of signed message can produce digital signature as evidence to convince third party that the signature was actually generated by the claimed signer. Most of the signature algorithm is combination of one way hash functions (OWHF) and public key cryptography (PKC). The OWHF is used to create message digest, then the signature is generated using the secret key of the signer. The public key of the signer can be verified by anyone and OWHF helps to check validity of the signature received.
Nowadays the popular cryptocurrency systems [3]–[5] and blockchain based systems technology [6], [7] have used in ECDSA [8]–[10]. Recently, Wei [11] proposed a multiple elliptic curves digital signature algorithm (MECDSA). The EC’s are used for Bitcoin technology and became popular due to its several beneficial properties. However, it cannot prevent the EC creator from inserting any backdoors into the curve. We proposed a mECDSA, which is more secure and help to avoid any backdoors. In proposed mECDSA scheme, the user can selects the number of EC as per his need and he is also able to customize the parameters of the EC. In proposed mECDSA we used a variant [12] of ECDSA, which helps to keep same security level by reducing the computational complexity.
In next Section, we briefly explain preliminaries. In Section III, we explain the basic ECDSA scheme. Next Section IV is about variant [12] of ECDSA. We proposed a new mECDSA based on variant [12] of ECDSA in Section V. Further in next Section, we give security and computational analysis of proposed scheme. In last Section we conclude our work.
II. PRELIMINARIES:
Elliptic Curve Cryptosystem (ECC) was introduced by Victor Miller [13] and Neal Koblitz [8], independently in 1985. There is an extensive literature on elliptic curves. They arise naturally in many branches of mathematics and are closely linked with the theory of elliptic functions, from which they derive their name.
Elliptic Curve (EC):
Let GF (p), be a prime field and let a, b GF (p) are constant such that 4a3 + 27b2 = 0. An EC E(a, b), over GF (p) is defined as the set of points (x, y) ∈ GF (p) ∗ GF (p) which satisfy the equation:
y2 = x3 + Ax + B
together with a special point O, called the point at infinity, where A and B are constants. This will referred as weierstrass equation for an EC.
Elliptic Curve Discrete Logarithm Problem (ECDLP):
For a group G, the ECDLP is to find the integer x, for group elements P and Q, such that Q = xP .
ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM Modern days technology rely on algorithms that do computation quickly. One of them is ECDSA which is the EC analogue of the Digital Signature Algorithm (DSA). The ECDSA was first proposed in 1992 by Scott Vanstone [14]. It was accepted in 1999 as an ANSI standard and in 2000 as IEEE and NIST standards. It was also accepted in 1998 as an ISO standard and is under consideration for inclusion in some other ISO standards. Organizations go for ECDSA because of robust security and no substantial weaknesses or threat have been found.
The ECDSA consist of three phases (A) Parameter or key Generation (B) Signature Generation and (C) Signature Verification.
(A) Parameter Generation:
The suitable chosen EC defined over a finite field Fp of characteristic p, and a base point G Ep(a, b) with order n.
(i) Select a random integer d such that 1 d n 1.
(ii) Compute Q = dG.
So public key pair is (Q, d).
(B) Signature Generation:
To sign a message m, signer follows the steps:
(i) Select an integer α such that 1 α n 1.
(ii) Compute αG = (x1, y1).
(iii) r = x1 mod n, If r = 0, then select new α.
(iv) Calculate α−1 mod n and e = h(m).
(v) Compute s = α−1(e + dr), if s = 0 then go to step (i).
The signature for the message m is (r, s).
(C) Signature Verification:
To verify signature (r, s) of message m, verifier V
follows the steps:
(i) Verifier checks whether r, s [1, n 1].
(ii) Compute e = h(m) and s−1.
(iii) Compute u = es−1 mod n and v = rs−1 mod n.
(iv) Compute w = (x2, y2) = uG + vQ, if w = 0 then stop, otherwise compute t = x2 mod n.
(v) The signature is valid if and only if t = r.
Proof of verification process:
αG = s−1(e + dr)G mod n
= s−1eG + s−1rdG mod n .
= uG + vQ mod n
Therefore uG + vQ = αG and so t = r, which is requisite.
III. VARIANT OF ECDSA:
The variant of ECDSA given in [12] also consist of three phases (A) Parameter or key Generation (B) Signature Generation and (C) Signature Verification.
(A) Parameter Generation:
The suitable chosen EC is defined over a finite field Fp of characteristic p and a base point G Ep(a, b) with order n.
(i) Select a random integer d such that 1 d n 1.
(ii) Compute Q = dG.
So public key pair is (Q, d).
(B) Signature Generation:
To sign a message m, signer follows the steps:
(i) Select an integer α such that 1 α n 1.
(ii) Compute αG = (x1, y1).
(iii) r = x1 mod n, If r = 0, then select new α.
(iv) Calculate e = h(m).
(v) Compute s = (ed + α), if s = 0 then go to step (i). The signature for the message m is (r, s).
(C) Signature Verification:
To verify signature (r, s) of message m, verifier V
follows the steps:
(i) Verifier checks whether r, s [1, n 1].
(ii) Compute e = h(m).
(iii) Compute w = (x2, y2) = sG eQ, if w = 0 then stop, otherwise compute v = x2 mod n.
(iv) The signature is valid if and only if v = r.
Proof of verification process:
αG = (s − ed)G mod n
= sG − edG mod n .
= sG − eQ mod n
Therefore sG eQ = αG and so v = r, which is requisite.
IV. MULTIPLE ELLIPTIC CURVES DIGITAL SIGNATURE ALGORITHM:
In this section to get rid of backdoors in EC used, we propose a mECDSA algorithm. Using this algorithm the user can selects number of EC as per his requirements and also selects the curve by altering its default parameters.
(A) mECDSA Signature Generation
The signer follows the below mentioned steps to signs the message:
(a) Compute e = h(m), where h is secure OWHF.
(b) 
Chooses random number αi [1,
ni 1], the compute
αi Gi = (xi1, yi1), where i = 1, 2, 3, , t.
(c) Compute ri = xi mod ni. If ri = 0, the reselect αi, where i = 1, 2, 3, , t.
(d) Compute r = r1 + r2 + r3 + + rt. Now if r = 0, the again reselect ki, where i = 1, 2, 3, , t.
(e) Then compute si = (edi + αi) mod ni. Now if si = 0, then reselect ki, where i = 1, 2, 3, · · · , t.
Finally (r, s1, s2, s3, · · · , st) is the signature for message m.
(B) mECDSA Signature Verification
The signature verifier can follow the below mentioned steps to verify signature:
(a) 
First of all V verify that r and si
are integers in [t, n1 + n2 + + nt t]
and [1, ni 1] respectively, where i = 1, 2,
3, , t, if not then signature is invalid one.
(b) Compute e = h(m), where h is same secure OWHF.
(c) Now compute Ri = si · Gi − e · Qi, where i = 1, 2, 3, · · · , t.
(d) 
Finally compute rij = xi
mod ni, where i = 1, 2, 3,
, t. Now if rj =
r1j + r2j + r3j + rtj . If r = rj then only the signature is valid one.
V. SECURITY AND COMPUTATIONAL ANALYSIS:
This section is subdivided into two parts (A) First we discuss about cryptographic security of proposed scheme and
(B) Secondly we analyze computational performance of our scheme.
A. Security Analysis:
The cryptographic security of PKC’s using EC rely on the intractable mathematical problem i.e. discrete logarithm prob- lem (DLP). The EC don’t have sub-exponential-time algorithm to solve ECDLP. The security of the proposed mECDSA is based on the intractability of ECDLP and it resists the following attacks-
(1) The adversary try to obtain secret key d1, d2,
, dt, with all the relevant information available in public
domain. In this situation the adversary can compute r1, r2, ·
· · , rt
with the help of known public key Q1, Q2, · · · ,
Qt. Now the signature (r, s , s , s , · · · , s )
and corresponding message m and then further calculate Gi,
where
βi = αiGi. If an adversary attempts to
find secret key then he would have to solve Qi = di
Gi or βi = αiGi
respectively for di and αi, which
is infeasible due to intractability of ECDLP.
(2) 
The adversary attempt to get the secret key di1 , di2 , · · · , dit1 from partial secret key dj , dj
, · · · , dj , due to backdoors in t2, (t2 <
t) in EC, for this he required to solve Qi = di
Gi or
βi = αiGi respectively for di and αi, which is infeasible due to intractability of ECDLP.
B. Computational Analysis:
In this sub section the computational analysis of the pro- posed mECDSA is discussed and compared with computa- tional cost of other existing schemes. To represent computa- tional complexity, we use notations A, M and I for simple addi- tion, multiplication and inversion operations respectively. The notations EA, EM are used for elliptic addition and elliptic multiplication operations respectively. The table below shows the computational analysis of MECDSA and mECDSA, which shows that our scheme required less number of computational operations.
Table I Computational Complexity Comparison
|
Method |
Process |
A |
M |
I |
EA |
EM |
|
ECDSA |
Sign Gen |
t |
2t |
t |
0 |
t |
|
|
Sign Ver |
0 |
2t |
t |
t |
2t |
|
vECDSA |
Sign Gen |
t |
t |
0 |
0 |
t |
|
|
Sign Ver |
0 |
0 |
0 |
t |
2t |
|
MECDSA |
sign Gen |
2t − 1 |
2t |
t |
0 |
t |
|
|
Sign Ver |
t − 1 |
2t |
t |
t |
2t |
|
mECDSA |
sign Gen |
2t − 1 |
t |
0 |
0 |
t |
|
|
Sign Ver |
t − 1 |
0 |
0 |
t |
2t |
VI. CONCLUSION:
In this paper in order to avoid backdoor in the EC of cryptocurrency systems, we proposes a mECDSA algorithm. This algorithm not only allows the signer selects the number of EC, but also specify the parameters of each EC. To get better performance regarding security and efficiency the systems based on blockchain should opt for two EC.
VII. ACKNOWLEDGMENT:
This work was financially supported in category of Col- laborative Research Project Under TEQIP-III, CSVTU Bhilai, C.G., with Grant Number: CSVTU/CRP/TEQIP-III/76, Dated: 05.09.2019. The authors also express their gratitude towards different anonymous reviewer for their comments and sugges- tions towards this work.
VIII. REFERENCES:
1. Stallings, William. Cryptography and network security, 4th ed., Pearson Education India, 2006.
2. Blake, Ian F., Gadiel Seroussi, and Nigel P. Smart, eds. Advances in elliptic curve cryptography. Vol. 317. Cambridge University Press, 2005.
3. Ujan Mukhopadhyay, Anthony Skjellum, Oluwakemi Hambolu, Jon Oakley, Lu Yu, Rich – ard Brooks. A brief survey of Cryptocurrency Systems. 14th Annual Conference on Privacy, Securiy and Trust, 2016, pp. 745-752.
4. Andreas M. Antonopoulos. Mastering Bitcoin. Second Edition, 2017.
5. Vujicic, Dejan, Dijana Jagodic, and Sinisa Randic. Blockchain technol- ogy, bitcoin, and Ethereum: A brief overview. 2018 17th international symposium infoteh-jahorina (infoteh). IEEE, 2018.
6. Alphand, Olivier, et al. IoTChain: A blockchain security architecture for the Internet of Things. 2018 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2018.
7. Yavuz, Emre, et al. Towards secure e-voting using ethereum blockchain. 2018 6th International Symposium on Digital Forensic and Security (ISDFS). IEEE, 2018.
8. Koblitz, Neal. Elliptic curve cryptosystems. Mathematics of computation 48.177 (1987): pp. 203-209.
9. A. Mennezes, S. Vanstone. Elliptic Curve Systems. Proposed IEEE P1363 standard, 1995, pp. 1-42.
10. Caelli, William J., Edward P. Dawson, and Scott A. Rea. PKI, elliptic curve cryptography, and digital signatures. Computers and Security 18.1 (1999): pp. 47-66.
11. Bi, Wei, Xiaoyun Jia, and Maolin Zheng. A Secure Multiple Elliptic Curves Digital Signature Algorithm for Blockchain. arXiv preprint arXiv:1808.02988 (2018).
12. Long, Tao, and Xiaoxia Liu. Two Improvements to Digital Signature Scheme Based on the Elliptic Curve Cryptosystem. Proceedings. The 2009 International Workshop on Information Security and Application (IWISA 2009). Academy Publisher, 2009.
13. Miller V. S., Use of elliptic curves in cryptography. In Advances in Cryptology-CRYPTO’85, Santa Barbara, CA, 1985, Lecture Notes in Comput. Sci., 218, Springer-Verlag, Berlin, (1986), 417–426.
14. Vanstone S. A., Responses to NIST’s proposal. Commun. ACM, 35, (1992), pp. 50–52.
|
Received on 22.05.2020 Accepted on 17.06.2020 © EnggResearch.net All Right Reserved Int. J. Tech. 2020; 10(1):93-96. DOI: 10.5958/2231-3915.2020.00018.8 |
|